package demo.collections;

/**
 * �Զ����������
 *
 * @author zjn
 *
 */
public class MyLink {
	Node head = null; // ͷ�ڵ�

	/**
	 * �����еĽڵ㣬data����ڵ��ֵ��next��ָ����һ���ڵ������
	 *
	 * @author zjn
	 *
	 */
	class Node {
		Node next = null;// �ڵ�����ã�ָ����һ���ڵ�
		int data;// �ڵ�Ķ��󣬼�����

		public Node(int data) {
			this.data = data;
		}
	}

	/**
	 * �������в�������
	 *
	 * @param d
	 */
	public void addNode(int d) {
		Node newNode = new Node(d);// ʵ����һ���ڵ�
		if (head == null) {
			head = newNode;
			return;
		}
		Node tmp = head;
		while (tmp.next != null) {
			tmp = tmp.next;
		}
		tmp.next = newNode;
	}

	/**
	 * ��ͷ���������в�������
	 *
	 * @param d
	 */
	public void addNodeForHead(int d) {
		Node newNode = new Node(d);// ʵ����һ���ڵ�
		newNode.next = head;
		head = newNode;
	}

	/**
	 *
	 * @param index:ɾ����index���ڵ�
	 * @return
	 */
	public boolean deleteNode(int index) {
		if (index < 1 || index > length()) {
			return false;
		}
		if (index == 1) {
			head = head.next;
			return true;
		}
		int i = 1;
		Node preNode = head;
		Node curNode = preNode.next;
		while (curNode != null) {
			if (i == index) {
				preNode.next = curNode.next;
				return true;
			}
			preNode = curNode;
			curNode = curNode.next;
			i++;
		}
		return false;
	}

	/**
	 *
	 * @return ���ؽڵ㳤��
	 */
	public int length() {
		int length = 0;
		Node tmp = head;
		while (tmp != null) {
			length++;
			tmp = tmp.next;
		}
		return length;
	}

	/**
	 * �ڲ�֪��ͷָ��������ɾ��ָ���ڵ�
	 *
	 * @param n
	 * @return
	 */
	public boolean deleteNode11(Node n) {
		if (n == null || n.next == null)
			return false;
		int tmp = n.data;
		n.data = n.next.data;
		n.next.data = tmp;
		n.next = n.next.next;
		System.out.println("ɾ���ɹ���");
		return true;
	}

	public void printList() {
		Node tmp = head;
		while (tmp != null) {
			System.out.print(tmp.data + " ");
			tmp = tmp.next;
		}
		System.out.println();
	}

	/**
	 * ����ת
	 *
	 * @param head
	 * @return
	 */
	public Node ReverseIteratively(Node head) {
		Node pReversedHead = head;
		Node pNode = head;
		Node pPrev = null;
		while (pNode != null) {
			Node pNext = pNode.next;
			if (pNext == null) {
				pReversedHead = pNode;
			}
			pNode.next = pPrev;
			pPrev = pNode;
			pNode = pNext;
		}
		this.head = pReversedHead;
		return this.head;
	}

	/**
	 * ���ҵ�������м�ڵ�
	 *
	 * @param head
	 * @return
	 */
	public Node SearchMid(Node head) {
		Node p = this.head, q = this.head;
		while (p != null && p.next != null && p.next.next != null) {
			p = p.next.next;
			q = q.next;
		}
		System.out.println("Mid:" + q.data);
		return q;
	}

	/**
	 * ���ҵ��� ��k��Ԫ��
	 *
	 * @param head
	 * @param k
	 * @return
	 */
	public Node findElem(Node head, int k) {
		if (k < 1 || k > this.length()) {
			return null;
		}
		Node p1 = head;
		Node p2 = head;
		for (int i = 0; i < k; i++)// ǰ��k��
			p1 = p1.next;
		while (p1 != null) {
			p1 = p1.next;
			p2 = p2.next;
		}
		return p2;
	}

	/**
	 * ����
	 *
	 * @return
	 */
	public Node orderList() {
		Node nextNode = null;
		int tmp = 0;
		Node curNode = head;
		while (curNode.next != null) {
			nextNode = curNode.next;
			while (nextNode != null) {
				if (curNode.data > nextNode.data) {
					tmp = curNode.data;
					curNode.data = nextNode.data;
					nextNode.data = tmp;
				}
				nextNode = nextNode.next;
			}
			curNode = curNode.next;
		}
		return head;
	}

	/**
	 * ɾ���ظ��ڵ�
	 */
	public void deleteDuplecate(Node head) {
		Node p = head;
		while (p != null) {
			Node q = p;
			while (q.next != null) {
				if (p.data == q.next.data) {
					q.next = q.next.next;
				} else
					q = q.next;
			}
			p = p.next;
		}

	}

	/**
	 * ��β��ͷ������������õݹ鷽ʽʵ��
	 *
	 * @param pListHead
	 */
	public void printListReversely(Node pListHead) {
		if (pListHead != null) {
			printListReversely(pListHead.next);
			System.out.println("printListReversely:" + pListHead.data);
		}
	}

	/**
	 * �ж������Ƿ��л������������л�ʱ��β�ڵ���ͬ
	 *
	 * @param head
	 * @return
	 */
	public boolean IsLoop(Node head) {
		Node fast = head, slow = head;
		if (fast == null) {
			return false;
		}
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
			if (fast == slow) {
				System.out.println("�������л�");
				return true;
			}
		}
		return !(fast == null || fast.next == null);
	}

	/**
	 * �ҳ����������
	 *
	 * @param head
	 * @return
	 */
	public Node FindLoopPort(Node head) {
		Node fast = head, slow = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			if (slow == fast)
				break;
		}
		if (fast == null || fast.next == null)
			return null;
		slow = head;
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}
}
